#ifndef EIGHT_H
#define EIGHT_H
#include <iostream>
#include <queue>
#include <stdlib.h>
#include <string>
#include <vector>
#include <list>
class Eight
{
public:
    Eight()
    {
        visit = new bool[size];
        path = new std::list<char>[size];
        memset(visit, 0, size*sizeof (bool));
    }
    ~Eight(){
        delete []visit;
        delete []path;
    }

    const int factorial[9]={1, 1, 2, 6, 24, 120, 720, 5040, 40320};
    bool *visit;
    std::list<char> *path;
    const int size = 362880;
    inline int canto(const char *s)
    {
        int index = 0;
        for(int i = 0; i < 9; i++)
        {
            int count = 0;
            for(int j=i+1; j < 9; j++)
            {
                if(s[j]<s[i])
                    count++;
            }
            index += factorial[8-i]*count;
        }
        return index;
    }
    inline bool move(char orientation, char *s)
    {
        int dx,dy,ox,oy;
        switch (orientation) {
        case 'u':
            dy=-1;dx=0;break;
        case 'd':
            dy=1;dx=0;break;
        case 'l':
            dy=0;dx=-1;break;
        default:
            dy=0;dx=1;
        }
        for(int i = 0; i < 9; i++)
        {
            if(s[i]=='0')
            {
                ox=i%3;oy=i/3;
                dx+=ox;
                dy+=oy;
                if(dx<0||dx>2||dy<0||dy>2)
                    return false;
                std::swap(s[i], s[dy*3+dx]);
                return true;
            }
        }
        return false;
    }
    static void display(char *s)
    {
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++)
                std::cout<<s[i*3+j];
            std::cout<<std::endl;
        }

    }
    static void display(std::queue<char> p)
    {
        while (!p.empty()) {
            std::cout<<p.front();
            p.pop();
        }
    }
    static void display(std::list<char> p)
    {
        for(auto ite = p.begin(); ite != p.end(); ite++)
            std::cout<<*ite;
    }
    struct Grid{
        char s[9];
        Grid(const char *s)
        {
            set(s);
        }
        inline void set(const char *s)
        {
            memcpy(this->s, s, 9);
        }
        Grid& operator=(const Grid &g)
        {
            memcpy(s, g.s, 9);
            return *this;
        }
    };
    void bfs()
    {
        std::queue<Grid> path1;
        char start[9]={'1','2','3','4','5','6','7','8','0'};
        int index = canto(start);
        visit[index]=true;
        path1.push(Grid(start));
        while (!path1.empty()) {
            std::queue<Grid> path2;
            while (!path1.empty()) {

                Grid tg = path1.front();
                int oindex = canto(tg.s);
                Grid tgu=tg,tgd=tg,tgl=tg,tgr=tg;
                path1.pop();
                if(move('u', tgu.s))
                {
                    int index = canto(tgu.s);
                    if(!visit[index]){
                        visit[index]=true;
                        path[index]=path[oindex];
                        path[index].push_front('u');
                        path2.push(Grid(tgu.s));
                    }
                }
                if(move('d',tgd.s))
                {
                    int index = canto(tgd.s);
                    if(!visit[index]){
                        visit[index]=true;
                        path[index]=path[oindex];
                        path[index].push_front('d');
                        path2.push(Grid(tgd.s));
                    }
                }
                if(move('l',tgl.s))
                {
                    int index = canto(tgl.s);
                    if(!visit[index]){
                        visit[index]=true;
                        path[index]=path[oindex];
                        path[index].push_front('l');
                        path2.push(Grid(tgl.s));
                    }
                }
                if(move('r',tgr.s))
                {
                    int index = canto(tgr.s);
                    if(!visit[index]){
                        visit[index]=true;
                        path[index]=path[oindex];
                        path[index].push_front('r');
                        path2.push(Grid(tgr.s));
                    }
                }

            }
            path1=path2;
        }
    }

};

#endif // EIGHT_H
